1. Field of the Invention
The present invention relates to devices and methods for estimating a series of symbols.
According to a first aspect, the invention relates to a device and a method for estimating a series of symbols with reduced implementation, and to corresponding circuits and systems.
According to a second aspect, the invention relates to a method and a device for estimating a series of symbols using a conditional correction, and to associated systems.
The invention finds particular application in the decoding according to the “BCJR” algorithm proposed by Bahl, Cocke, Jellnek and Raviv and described in their article entitled “Optimal decoding of linear codes for minimizing symbol error rate”, in IEEE Transactions on Information Theory, March 1974, pages 284-287.
Thanks to the first aspect of the invention, the number of logic gates necessary for this algorithm may advantageously be reduced, for example in equipment of the FPGA (“Field Programmable Gate Array”) or ASIC (“Application-Specific Integrated Circuit”) type, in particular when the detector included in the decoder is constructed for calculating a posteriori probabilities in accordance with a “Log-MAP” (MAP standing for “Maximum A Posteriori”) algorithm, using Jacobian logarithms.
According to its second aspect, the invention, which belongs to the field of encoding/decoding, concerns a method of estimating received symbols which uses an algorithm of the “Log-MAP” type (MAP standing for “Maximum A Posteriori”), whose principle is stated below. It deals with the application, in certain cases, of a correction value in the context of the determination of the probabilities related to the states of the encoder, to remedy the degradation of the performance usually caused by quantisation in this type of decoding technique, as explained below.
The invention is described here more particularly in its application to turbodecoding, by way of example that is in no way limitative. The invention can be applied to other fields, such as for example the field of equalisation.
2. Description of the Related Art
Turbocodes are very advantageous in conditions of low signal to noise ratio (SNR). A conventional turbo-encoder is constituted by two recursive systematic convolutional encoders (RSC), and an interleaver, disposed as shown in FIG. 1. The turbo-encoder outputs three series of binary elements (x, y1, y2), where x is the so-called systematic output of the turbo-encoder, that is to say one which has undergone no processing compared with the input signal x, y1 is the output encoded by the first RSC encoder, and y2 is the output encoded by the second RSC encoder after passing through the interleaver.
For more details on turbocodes, reference can usefully be made to the article by C. Berrou, A. Glavieux and P. Thitimajshima entitled “Near Shannon limit error-correcting coding and decoding: turbo-codes”, ICC '93, Geneva, or to the article by C. Berrou and A. Glavieux entitled “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes”, in IEEE Transactions on Communications, vol. 44, No. 10, October 1996.
FIG. 2 depicts an example of a conventional turbodecoder able to decode data supplied by a turbo-encoder such as the one in FIG. 1. The inputs x′, y1′, y2′ of the turbodecoder are the outputs of the turbo-encoder altered by the transmission channel and the transmission and reception processes. The structure of such a turbodecoder is well known to persons skilled in the art and will therefore not be described in detail here.
It requires in particular two decoders, referred to as “Decoder 1” and “Decoder 2” in FIG. 2; these decoders can be of the BCJR type mentioned above or, as a variant, of the SOVA type (“Soft Output Viterbi Algorithm”).
A conventional turbodecoder also requires a loop back of the output of the deinterleaver π2 onto the input of the first decoder, in order to transmit the so-called “extrinsic” information from the second decoder to the first decoder.
Such a decoding system uses an exploration of the probabilities according to the chronological order of arrival of the symbols (first symbol received, first symbol decoded), but also in the opposite direction to this chronological order (last symbol received, first symbol decoded). This appears in the descriptive elements of the BCJR decoder below.
The actual structure of a MAP decoder at each time k uses not only the systematic (noisy) received data yks and the parities issuing from the encoder and received noisy ykp, but also an average of the noise σ and the extrinsic information coming from the other decoder.
The purpose of the decoding is to estimate the consecutive states of the encoder according to the knowledge that is available, that is to say from the sequence of noisy received information.
FIG. 3 illustrates such a decoder. The input yks of the MAP decoder corresponds to the input x′ of the turbodecoder illustrated in FIG. 2, the input ykp corresponds to the input y1′ or y2′ of FIG. 2 depending on whether it relates to decoder 1 or 2, and L'e corresponds to L4 or L2. The variable σ corresponds to the effective value of the noise. It is used in the decoder in the form of noise power, in order to normalise the values of yks and ykp.
If it is considered that the data are encoded not in binary (0 or 1) but in NRZ (Non-Return to Zero), that is to say with data transmitted on levels +1 or −1, the decoder seeks to decide whether the noisy received data was initially a “+1” or a “−1”.
Let ûk be the result of this decision, let uk be the original data sent and let Y be the complete sequence of received encoded information.
The decision is the following operation, denoting the probability as P:ûk=+1 if P(uk=+1|Y)>P(uk=−1|Y)ûk=−1 if P(uk=+1|Y)<P(uk=−1|Y)
Thus the decision ûk is given by the sign of the variable L(uk), defined as the Logarithm of the ratio of the A Posteriori Probabilities (LAPP).       L    ⁢          (              u        k            )        ⁢      =    ^    ⁢            ln      ⁢              (                              P            ⁢                          (                                                u                  k                                =                                                      +                    1                                    |                  Y                                            )                                            P            ⁢                          (                                                u                  k                                =                                                      -                    1                                    |                  Y                                            )                                      )              .  
Let S be the set of the possible states of the encoder.
Using the concept of code trellis:                               L          ⁡                      (                          u              k                        )                          =                  ln          (                                                    ∑                                  S                  +                                            ⁢                                                p                  ⁡                                      (                                                                                            s                                                      k                            -                            1                                                                          =                                                  s                          ′                                                                    ,                                                                        s                          k                                                =                        s                                                              )                                                  /                                  p                  ⁡                                      (                    Y                    )                                                                                                      ∑                                  S                  -                                            ⁢                                                p                  ⁡                                      (                                                                                            s                                                      k                            -                            1                                                                          =                                                  s                          ′                                                                    ,                                                                        s                          k                                                =                        s                                                              )                                                  /                                  p                  ⁡                                      (                    Y                    )                                                                                )                                    (        1        )            where:                skεS is the state of the encoder at time k,        S+ is the set of the pairs of states (s′,s) corresponding to all the transitions (sk−1=s′)→(sk=s) caused by an input of the encoder uk=+1, and        S− is defined in a similar manner for uk=−1.        
It can be seen that it is possible to eliminate p(Y) in equation (1). This means that only one algorithm is needed for calculating p(s′,s,Y)=p(sk−1=s′, sk=s, Y).
According to the BCJR algorithm,p(s′,s,Y)=αk−1(s′)γk(s′,s)βk(s)  (2)with:                                                         α              k                        ⁡                          (              s              )                                ⁢                      =            ^                    ⁢                                    p              ⁡                              (                                                                            s                      k                                        =                    s                                    ,                                      Y                    1                    k                                                  )                                      =                                          ∑                                                      s                    ′                                    ∈                  S                                            ⁢                                                                    α                                          k                      -                      1                                                        ⁡                                      (                                          s                      ′                                        )                                                  ⁢                                                      γ                    k                                    ⁡                                      (                                                                  s                        ′                                            ,                      s                                        )                                                                                      ⁢                                  ⁢                                            β                              k                -                1                                      ⁡                          (                              s                ′                            )                                ⁢                      =            ^                    ⁢                                    p              ⁡                              (                                                                            Y                                              k                        +                        1                                            N                                        ❘                                          s                      k                                                        =                  s                                )                                      =                                          ∑                                  s                  ∈                  S                                            ⁢                                                                    β                    k                                    ⁡                                      (                    s                    )                                                  ⁢                                                      γ                    k                                    ⁡                                      (                                                                  s                        ′                                            ,                      s                                        )                                                                                      ⁢                                  ⁢                                            γ              k                        ⁡                          (                                                s                  ′                                ,                s                            )                                ⁢                      =            ^                    ⁢                      p            ⁡                          (                                                                    s                    k                                    =                  s                                ,                                                                            y                      k                                        ❘                                          s                                              k                        -                        1                                                                              =                                      s                    ′                                                              )                                                          (        3        )             γk(s′,s){circumflex over (=)}p(sk=s,yk|sk−1=s′)where α and β represent the probabilities of obtaining the states S at time k. The probabilities α and β are calculated in a recursion, respectively starting from the initial state (that is to say the first symbols received), and starting from the final state (that is to say the last symbols received), with:α0(0)=1 and α0(s≈0)=0βN(0)=1 and βN(s≈0)=0if the encoder starts from a zero state and finishes in a zero state, the index N designating the length of the data frame received and therefore corresponding to the last symbol received. There are (N+1)×Ns values of probabilities α and N×Ns values of probabilities β, Ns being the number of possible states of the encoder. This is why the α are numbered from 0 to N and the β, from 1 to N.
The elimination of the factor p(Y) in equation (1) gives numerical instability. This can be avoided by using probabilities modified as follows:
 {tilde over (α)}k(s){circumflex over (=)}αk(s)/p(Y1k){tilde over (β)}k(s){circumflex over (=)}βk(s)/p(Yk+1N|Y1k)which can be re-written as follows:                                                                         α                ~                            k                        ⁡                          (              s              )                                =                                                    ∑                                  s                  ′                                            ⁢                                                                                          α                      ~                                                              k                      -                      1                                                        ⁡                                      (                                          s                      ′                                        )                                                  ⁢                                                      γ                    k                                    ⁡                                      (                                                                  s                        ′                                            ,                      s                                        )                                                                                                      ∑                s                            ⁢                                                ∑                                      s                    ′                                                  ⁢                                                                                                    α                        ~                                                                    k                        -                        1                                                              ⁡                                          (                                              s                        ′                                            )                                                        ⁢                                                            γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ,                        s                                            )                                                                                                          ⁢                                  ⁢                                                            β                ~                                            k                -                1                                      ⁡                          (                              s                ′                            )                                =                                                    ∑                s                            ⁢                                                                                          β                      ~                                        k                                    ⁡                                      (                    s                    )                                                  ⁢                                                      γ                    k                                    ⁡                                      (                                                                  s                        ′                                            ,                      s                                        )                                                                                                      ∑                                  s                  ′                                            ⁢                                                ∑                  s                                ⁢                                                                                                    β                        ~                                            k                                        ⁡                                          (                      s                      )                                                        ⁢                                                            γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ,                        s                                            )                                                                                                                              (        4        )            
Dividing equation (2) by p(Y)/p(yk)=p(Y1k−1)·p(Yk +1N|Y1k), there is obtained:p(s′,s|Y)/p(yk)={tilde over (α)}k−1(s′)γk(s′,s){tilde over (β)}k(s)  (5)
Now the BCJR-MAP algorithm amounts to calculating the LAPP, defined above and denoted L(uk), by combining equations (1) and (5):                               L          ⁡                      (                          u              k                        )                          =                  ln          ⁡                      (                                                            ∑                                      S                    +                                                  ⁢                                                                                                    α                        ~                                                                    k                        -                        1                                                              ⁡                                          (                                              s                        ′                                            )                                                        ⁢                                                            γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ,                        s                                            )                                                        ⁢                                                                                    β                        ~                                            k                                        ⁡                                          (                      s                      )                                                                                                                    ∑                                      S                    -                                                  ⁢                                                                                                    α                        ~                                                                    k                        -                        1                                                              ⁡                                          (                                              s                        ′                                            )                                                        ⁢                                                            γ                      k                                        ⁡                                          (                                                                        s                          ′                                                ,                        s                                            )                                                        ⁢                                                                                    β                        ~                                            k                                        ⁡                                          (                      s                      )                                                                                            )                                              (        6        )            the probabilities α and the β being calculated recursively by equation (4).
Let this result be applied to the turbocodes, for a parallel iterative convolutional code, in an additive white Gaussian noise (AWGN) channel. By the Bayes theorem, the LAPP of the MAP decoder can be written;       L    ⁢          (              u        k            )        =            ln      ⁢              (                              P            ⁢                          (                                                Y                  |                                      u                    k                                                  =                                  +                  1                                            )                                            P            ⁢                          (                                                Y                  |                                      u                    k                                                  =                                  -                  1                                            )                                      )              +          ln      ⁢              (                              P            ⁢                          (                                                u                  k                                =                                  +                  1                                            )                                            P            ⁢                          (                                                u                  k                                =                                  -                  1                                            )                                      )            where the second term of the sum represents the a priori information. Given that in general P(uk+1)=P(uk=−1), the a priori information is zero for convolution encoders.
However, in an iterative decoder, the decoder 1 (denoted D1) receives extrinsic information or a soft decision for each uk coming from decoder 2 (denoted D2), which serves as a priori information for D1, which initiates the mechanism D1→D2→D1→ . . . , the decoder delivering a soft decision at each half-iteration for the following decoder (except for the first decoding). These soft decisions result from the use of two different encoders after interleaving; they are therefore decorrelated.
A description is now given of a way of obtaining this extrinsic information, from equation (3), γk(s′,s) can be written:γk(s′,s)=P(s|s′)p(yk|s′,s)=P(uk)p(yk|uk)  (7)
Defining:                                           L            e                    ⁡                      (                          u              k                        )                          ⁢                  =          ^                ⁢                  ln          ⁡                      (                                          P                ⁡                                  (                                                            u                      k                                        =                                          +                      1                                                        )                                                            P                ⁡                                  (                                                            u                      k                                        =                                          -                      1                                                        )                                                      )                                              (        8        )            it is possible to write:                                           P            ⁡                          (                              u                k                            )                                =                                    (                                                exp                  ⁡                                      (                                                                  -                                                                              L                            e                                                    ⁡                                                      (                                                          u                              k                                                        )                                                                                              /                      2                                        )                                                                    1                  +                                      exp                    ⁡                                          (                                              -                                                                              L                            e                                                    ⁡                                                      (                                                          u                              k                                                        )                                                                                              )                                                                                  )                        ⁢                          exp              ⁡                              (                                                      u                    k                                    ⁢                                                                                    L                        e                                            ⁡                                              (                                                  u                          k                                                )                                                              /                    2                                                  )                                                                                  =                                    A              k                        ⁢                          exp              ⁡                              (                                                      u                    k                                    ⁢                                                                                    L                        e                                            ⁡                                              (                                                  u                          k                                                )                                                              /                    2                                                  )                                                                                                  p            ⁡                          (                                                y                  k                                |                                  u                  k                                            )                                ∝                    ⁢                      exp            ⁡                          (                                                                    -                                                                  (                                                                              y                            k                            s                                                    -                                                      u                            k                                                                          )                                            2                                                                            2                    ⁢                                          σ                      2                                                                      -                                                                            (                                                                        y                          k                          p                                                -                                                  x                          k                          p                                                                    )                                        2                                                        2                    ⁢                                          σ                      2                                                                                  )                                                                    =                    ⁢                                    B              k                        ⁢                          exp              ⁡                              (                                                                                                    u                        k                                            ⁢                                              y                        k                        s                                                              +                                                                  y                        k                        p                                            ⁢                                              x                        k                        p                                                                                                  σ                    2                                                  )                                                        where yks is the systematic data item received and ykp is the corresponding parity issuing from the encoder, at time k.
Then:             γ      k        ⁢          (                        s          ′                ,        s            )        ∝            A      k        ⁢          B      k        ⁢          exp      ⁢              (                              u            k                    ⁢                                                    L                e                            ⁢                              (                                  u                  k                                )                                      /            2                          )              ⁢          exp      ⁢              (                                                            u                k                            ⁢                              y                k                s                                      +                                          y                k                p                            ⁢                              x                k                p                                                          σ            2                          )            
Now, γk(s′,s) appears in the numerator and denominator of equation (6). The factor AkBk disappears since it is independent of uk.
Let 2Ec/N0=1/σ2 and σ2=N0/2Ec, where Ec=RcEb is the energy per bit, since symbols {−1,+1} are transmitted in the channel, N0 being the energy of the noise of the channel. In equation (7), the following can be derived:                                                                                                               γ                    k                                    ⁡                                      (                                                                  s                        ′                                            ,                      s                                        )                                                  ∼                                ⁢                                                      exp                    ⁡                                          (                                                                                                    1                            2                                                    ⁢                                                                                    u                              k                                                        ⁡                                                          (                                                                                                L                                  e                                                                ⁢                                                                  u                                  k                                                                                            )                                                                                                      +                                                                              L                            c                                                    ⁢                                                      y                            k                            s                                                                                              )                                                        +                                                            1                      2                                        ⁢                                          u                      k                                        ⁢                                          L                      c                                        ⁢                                          y                      k                      p                                        ⁢                                          x                      k                      p                                                                                                                                              =                                ⁢                                                      exp                    ⁡                                          (                                                                        1                          2                                                ⁢                                                                              u                            k                                                    ⁡                                                      (                                                                                                                            L                                  e                                                                ⁡                                                                  (                                                                      u                                    k                                                                    )                                                                                            +                                                                                                L                                  c                                                                ⁢                                                                  y                                  k                                  s                                                                                                                      )                                                                                              )                                                        ⁢                                                            γ                      k                      e                                        ⁡                                          (                                                                        s                          ′                                                ,                        s                                            )                                                                                                          ⁢                                  ⁢                  with:                ⁢                                  ⁢                                            γ              k              e                        ⁡                          (                                                s                  ′                                ,                s                            )                                ⁢                      =            ^                    ⁢                      exp            ⁡                          (                                                1                  2                                ⁢                                  L                  c                                ⁢                                  y                  k                  p                                ⁢                                  x                  k                  p                                            )                                      ⁢                                  ⁢                              L            c                    ⁢                      =            ^                    ⁢                                    4              ⁢                              E                c                                                    N              0                                      ⁢                                  ⁢                              By            ⁢                                                   ⁢            combining            ⁢                                                   ⁢                          (              8              )                        ⁢                                                   ⁢            and            ⁢                                                   ⁢                          (              9              )                                ,                      there            ⁢                                                   ⁢            is            ⁢                                                   ⁢            obtained            ⁢                          :                                                          (        9        )                                                                                    L                ⁡                                  (                                      u                    k                                    )                                            =                            ⁢                              ln                ⁡                                  (                                                                                    ∑                                                  S                          +                                                                    ⁢                                                                                                                                  α                              ~                                                                                      k                              -                              1                                                                                ⁡                                                      (                                                          s                              ′                                                        )                                                                          ⁢                                                                              γ                            k                            e                                                    ⁡                                                      (                                                                                          s                                ′                                                            ,                              s                                                        )                                                                          ⁢                                                                                                            β                              ~                                                        k                                                    ⁡                                                      (                            s                            )                                                                          ⁢                                                  C                          k                                                                                                                                    ∑                                                  S                          -                                                                    ⁢                                                                                                                                  α                              ~                                                                                      k                              -                              1                                                                                ⁡                                                      (                                                          s                              ′                                                        )                                                                          ⁢                                                                              γ                            k                            e                                                    ⁡                                                      (                                                                                          s                                ′                                                            ,                              s                                                        )                                                                          ⁢                                                                                                            β                              ~                                                        k                                                    ⁡                                                      (                            s                            )                                                                          ⁢                                                  C                          k                                                                                                      )                                                                                                        =                            ⁢                                                                    L                    c                                    ⁢                                      y                    k                    s                                                  +                                                      L                    e                                    ⁡                                      (                                          u                      k                                        )                                                  +                                  ln                  ⁡                                      (                                                                                            ∑                                                      S                            +                                                                          ⁢                                                                                                                                            α                                ~                                                                                            k                                -                                1                                                                                      ⁡                                                          (                                                              s                                ′                                                            )                                                                                ⁢                                                                                    γ                              k                              e                                                        ⁡                                                          (                                                                                                s                                  ′                                                                ,                                s                                                            )                                                                                ⁢                                                                                                                    β                                ~                                                            k                                                        ⁡                                                          (                              s                              )                                                                                                                                                                            ∑                                                      S                            -                                                                          ⁢                                                                                                                                            α                                ~                                                                                            k                                -                                1                                                                                      ⁡                                                          (                                                              s                                ′                                                            )                                                                                ⁢                                                                                    γ                              k                              e                                                        ⁡                                                          (                                                                                                s                                  ′                                                                ,                                s                                                            )                                                                                ⁢                                                                                                                    β                                ~                                                            k                                                        ⁡                                                          (                              s                              )                                                                                                                                            )                                                                                                          (        10        )            
The second equality in equation (10) above is justified by the fact that the quantity       C    k    ⁢      =    ^    ⁢      exp    ⁢          (                        1          2                ⁢                              u            k                    ⁢                      (                                                            L                  e                                ⁢                                  (                                      u                    k                                    )                                            +                                                L                  c                                ⁢                                  y                  k                  s                                                      )                              )      can be put as a factor in the summations of the numerator and denominator.
The last term of equation (10) represents the extrinsic information passed from one decoder to the other. The final decision can be obtained on the basis of the following formula:L1(uk)=Lcyks+L2→1e(uk)+L1→2e(uk)where L2→1e(uk) is the extrinsic information transmitted from D2 to D1 and L1→2e(uk) is the extrinsic information transmitted from D1 to D2.
In general terms, upon hardware implementation of a function, a person skilled in the art seeks to avoid multiplications, which are expensive in terms of surface area of silicon. It is well known that the hardware cost is an increasing function of the surface area of silicon engaged in implementing a function. A person skilled in the art generally seeks a balance between the speed of execution of the function and the resulting surface area of silicon.
To avoid the use of multipliers, it is known that use can be made of the natural logarithm of the calculation functions for the probabilities α and β defined above:                                                                         α                ≂                            k                        ⁡                          (              s              )                                =                                    ln              ⁡                              (                                                      ∑                                          s                      ′                                                        ⁢                                      exp                                                                                                                        α                            ≂                                                                                k                            -                            1                                                                          ⁡                                                  (                                                      s                            ′                                                    )                                                                    +                                                                                                    γ                            _                                                    k                                                ⁡                                                  (                                                                                    s                              ′                                                        ,                            s                                                    )                                                                                                                    )                                      -                          ln              ⁡                              (                                                      ∑                    s                                    ⁢                                                            ∑                                              s                        ′                                                              ⁢                                          exp                                                                                                                                  α                              ≂                                                                                      k                              -                              1                                                                                ⁡                                                      (                                                          s                              ′                                                        )                                                                          +                                                                                                                                            γ                                _                                                            ⁢                                                                                                                                                     k                                                    ⁢                                                      (                                                                                          s                                ′                                                            ,                              s                                                        )                                                                                                                                              )                                                    ⁢                                  ⁢                                                            β                ≂                                            k                -                1                                      ⁡                          (                              s                ′                            )                                =                                    ln              ⁡                              (                                                      ∑                    s                                    ⁢                                      exp                                                                                                                        β                            ≂                                                    k                                                ⁡                                                  (                          s                          )                                                                    +                                                                                                                                  γ                              _                                                        ⁢                                                                                                                                           k                                                ⁢                                                  (                                                                                    s                              ′                                                        ,                            s                                                    )                                                                                                                    )                                      -                          ln              ⁡                              (                                                      ∑                                          s                      ′                                                        ⁢                                                            ∑                      s                                        ⁢                                          exp                                                                                                                                  β                              ≂                                                        k                                                    ⁡                                                      (                            s                            )                                                                          +                                                                                                                                            γ                                _                                                            ⁢                                                                                                                                                     k                                                    ⁢                                                      (                                                                                          s                                ′                                                            ,                              s                                                        )                                                                                                                                              )                                                    ⁢                                  ⁢                                                            γ                _                            k                        ⁡                          (                                                s                  ′                                ,                s                            )                                ∼                                                    1                2                            ⁢                                                u                  k                                ⁡                                  (                                                                                    L                        e                                            ⁡                                              (                                                  u                          k                                                )                                                              +                                                                  L                        c                                            ⁢                                              y                        k                        s                                                                              )                                                      +                                                            γ                  _                                k                e                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                                    ⁢                                  ⁢                                                            γ                _                            k              e                        ⁡                          (                                                s                  ′                                ,                s                            )                                ⁢                      =            ^                    ⁢                                    ln              ⁡                              (                                                      γ                    k                    e                                    ⁡                                      (                                                                  s                        ′                                            ,                      s                                        )                                                  )                                      =                                                            1                  2                                ⁢                                  L                  c                                ⁢                                  y                  k                  p                                ⁢                                  x                  k                  p                                ⁢                                                                   ⁢                and                ⁢                                                                   ⁢                                  L                  c                                            ⁢                              =                ^                            ⁢                                                4                  ⁢                                      E                    c                                                                    N                  0                                                                                        (        11        )            
The output obtained is the log likelihood:                                           L            e                    ⁡                      (                          u              k                        )                          =                              ln            ⁡                          (                                                ∑                                      S                    +                                                  ⁢                                  exp                                                                                                              α                          ≂                                                                          k                          -                          1                                                                    ⁡                                              (                                                  s                          ′                                                )                                                              +                                                                                            γ                          _                                                k                        e                                            ⁡                                              (                                                                              s                            ′                                                    ,                          s                                                )                                                              +                                                                                            β                          ≂                                                k                                            ⁡                                              (                        s                        )                                                                                                        )                                -                      ln            ⁡                          (                                                ∑                                      S                    -                                                  ⁢                                  exp                                                                                                              α                          ≂                                                                          k                          -                          1                                                                    ⁡                                              (                                                  s                          ′                                                )                                                              +                                                                                            γ                          _                                                k                        e                                            ⁡                                              (                                                                              s                            ′                                                    ,                          s                                                )                                                              +                                                                                            β                          ≂                                                k                                            ⁡                                              (                        s                        )                                                                                                        )                                                          (        12        )            
From this finding, obtaining the probabilities related to the nodes of the trellis amounts to calculating the quantity:ΔN=ln(expδ0+expδ1 + . . . expδi+ . . . expδNwhere N designates the length of the data frame received and where δi, for i=0 to Ns, is equal for example to {tilde over({overscore (α)})}k−1(s′)+{overscore (γ)}(s′,s), or {tilde over({overscore (β)})}k−1(s′)+{overscore (γ)}(s′,s), etc.
This quantity is calculated recursively, using the Jacobian logarithm; the recursion formula can be written as follows:Δi=ln(expΔi−1+expδi)=max(Δi−1, δi)+fc(|Δi−1−δi|)  (13)withΔ1=ln(expδ1)=δ1andfc(x)=ln(1+exp−x), x>0
Since this equation is not an approximation, there is no loss of information when use is made of the Jacobian logarithm and additions, instead of multiplications.
In summary, it can also be stated that the decoding is carried out on the basis of a calculation concerning probabilities related to the states of the encoder, using a metric consisting both of a Euclidian distance calculation and the information obtained at the previous iteration. This metric is the term γ defined above.
The states of the encoder are calculated by observing the effects of the previous states on the current state, taking account of the metric, which gives the probabilities α.
Likewise, the states of the encoder are obtained by observing the effects of the subsequent states on the current state, taking account of the metric, which gives the probabilities β.
From these probabilities and the metric, a measurement is obtained which is the log likelihood of the symbol belonging to one or other of the elements of the NRZ alphabet.
With the help of FIGS. 4 and 5, two examples are now described of the embodiment of such a decoder in the prior art, in particular with regard to the calculation of probabilities.
In these figures, the variables α and β designate the probabilities defined above, the variable J designates the Jacobian logarithm and the variable Lke is identical to the variable Le(uk) defined by equation (8) given above.
The first embodiment of the prior art illustrated in FIG. 4 includes essentially a Jacobian logarithm calculator and three memory registers for storing the results of the calculations corresponding respectively to the three quantities Lke, αk and βk−1.
The second embodiment of the prior art illustrated in FIG. 5 also includes a multiplexer (with appropriate connections) and a state machine controlling this multiplexer.
The prior art precludes the possibility of using the same calculation circuit for the aforementioned three quantities, since equations (11) and (12) given above use neither the same number of operands nor the same states.